package list

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

// Problem Definition: https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4

func shoppingList() {
	reader := bufio.NewReader(os.Stdin)
	line, _ := reader.ReadString('\n')
	line = strings.TrimSuffix(line, "\n")
	arr := strings.Split(line, " ")
	N, _ := strconv.Atoi(arr[0])
	N /= 10
	m, _ := strconv.Atoi(arr[1])
	prices := make([][3]int, m+1)
	priority := make([][3]int, m+1)
	for i := 1; i <= m; i++ {
		line, _ = reader.ReadString('\n')
		line = strings.TrimSuffix(line, "\n")
		arr = strings.Split(line, " ")

		a, _ := strconv.Atoi(arr[0])
		a /= 10
		b, _ := strconv.Atoi(arr[1])
		b *= a
		c, _ := strconv.Atoi(arr[2])
		if c == 0 {
			prices[i][0] = a
			priority[i][0] = b
		} else {
			if prices[c][1] == 0 {
				prices[c][1] = a
				priority[c][1] = b
			} else {
				prices[c][2] = a
				priority[c][2] = b
			}
		}
	}

	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, N+1)
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= N; j++ {
			a, b := prices[i][0], priority[i][0]
			c, d := prices[i][1], priority[i][1]
			e, f := prices[i][2], priority[i][2]

			dp[i][j] = dp[i-1][j]

			if j >= a {
				dp[i][j] = max(dp[i][j], dp[i-1][j-a]+b)
			}
			if j >= a+c {
				dp[i][j] = max(dp[i-1][j-a-c]+b+d, dp[i][j])
			}
			if j >= a+e {
				dp[i][j] = max(dp[i-1][j-a-e]+b+f, dp[i][j])
			}
			if j >= a+c+e {
				dp[i][j] = max(dp[i-1][j-a-c-e]+b+d+f, dp[i][j])
			}
		}
	}

	fmt.Println(dp[m][N] * 10)
}
